翻訳と辞書 Words near each other ・ Computer compatibility ・ Computer component ・ Computer conferencing ・ Computer configuration ・ Computer Conflict ・ Computer Conservation Society ・ Computer console ・ Computer Consoles Inc. ・ Computer Control Company ・ Computer Controlled Acoustic Instruments pt2 ・ Computer cooling ・ Computational Heuristic Intelligence ・ Computational human phantom ・ Computational humor ・ Computational immunology ・ Computational indistinguishability ・ Computational informatics ・ Computational Infrastructure for Geodynamics ・ Computational intelligence ・ Computational Intelligence (journal) ・ Computational irreducibility ・ Computational journalism ・ Computational law ・ Computational learning theory ・ Computational lexicology ・ Computational linguistics ・ Computational Linguistics (journal) ・ Computational lithography ・ Computational logic ・ Computational magnetohydrodynamics Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Computational indistinguishability ： ウィキペディア英語版 Computational indistinguishability In computational complexity, if $\backslash scriptstyle\backslash \_\_(A(x)\; =\; 1)\; -\; \backslash Pr\_(A(x)\; =\; 1)\; \backslash right|.$ denoted $D\_n\; \backslash approx\; E\_n\backslash !\backslash ,$.〔(Lecture 4 - Computational Indistinguishability, Pseudorandom Generators )〕 In other words, every efficient algorithm ''As behavior does not significantly change when given samples according to ''D''''n'' or ''E''''n'' in the limit as $n\backslash to\; \backslash infty$. Another interpretation of computational indistinguishability, is that polynomial-time algorithms actively trying to distinguish between the two ensembles cannot do so: That any such algorithm will only perform negligibly better than if one were to just guess. Implicit in the definition is the condition that the algorithm, $A$, must decide based on a single sample from one of the distributions. One might conceive of a situation in which the algorithm trying to distinguish between two distributions, could access as many samples as it needed. Hence two ensembles that cannot be distinguished by polynomial-time algorithms looking at multiple samples are deemed indistinguishable by polynomial-time sampling.〔Goldreich, O. (2003). Foundations of cryptography. Cambridge, UK: Cambridge University Press.〕 If the polynomial-time algorithm can generate samples in polynomial time, or has access to a random oracle that generates samples for it, then indistinguishability by polynomial-time sampling is equivalent to computational indistinguishability.〔 == References == 〔 * Donald Beaver and Silvio Micali and Phillip Rogaway, The Round Complexity of Secure Protocols (Extended Abstract), 1990, pp. 503–513 * Shafi Goldwasser and Silvio Micali. Probabilistic Encryption. JCSS, 28(2):270–299, 1984 * Oded Goldreich. Foundations of Cryptography: Volume 2 – Basic Applications. Cambridge University Press, 2004. * Jonathan Katz, Yehuda Lindell, "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Computational indistinguishability」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.